//剑指 Offer II 006. 排序数组中两个数字之和
//思路：因为是升序排序的整数数组，使用头尾双指针，时间复杂度为 O(N)
//1.让首尾位置的元素相加，等于 target，就把两个下标放入开辟的内存中
//2.不相等就循环，循环条件为 sum != target 
//不相等分两种情况（基于升序排序数组的前提）：1> 小于：让 begin 往后走一步
//										   2> 大于：让 end 往前走

#include <stdlib.h>
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int begin = 0, end = numbersSize - 1;
    int sum = numbers[begin] + numbers[end];

    while (sum != target)//不等于循环
    {
        if (sum < target)//小于的情况
            begin++;
        else//大于的情况
            end--;

        sum = numbers[begin] + numbers[end];
    }

    *returnSize = 2;
    int* ret = (int*)malloc(sizeof(int) * 2);
    if (ret == NULL)
        return NULL;
    ret[0] = begin;
    ret[1] = end;

    return ret;
}